from typing import List


class Solution:
    # 寻找所有候选数字的组合，使得组合中的数字和等于目标数
    # candidates 是候选数字列表，target 是目标数
    # 返回所有满足条件的数字组合
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 初始化结果列表
        res = []
        lll=0

        # 定义深度优先搜索函数
        # start 是当前搜索的起始索引，避免重复搜索
        # target 是当前剩余的目标数
        # path 是当前的数字组合
        def dfs(start, target, path):
            # 如果目标数为0，说明找到了一组满足条件的数字组合
            if target == 0:
                # 将当前组合添加到结果列表中
                res.append(path.copy())
                return
            # 如果目标数小于0，说明当前组合不满足条件，回溯
            if target < 0:
                return
            # 遍历候选数字列表，尝试所有可能的数字组合
            for i in range(start, len(candidates)):
                # 将当前数字添加到组合中
                path.append(candidates[i])
                # 递归调用深度优先搜索函数，更新目标数和组合
                dfs(i, target - candidates[i], path)
                print(1)

                # 回溯，将当前数字从组合中移除，尝试下一个数字
                path.pop()

        # 从第一个候选数字开始搜索
        dfs(0, target, [])
        # 返回所有满足条件的数字组合
        return res


lll = Solution()
print(lll.combinationSum([3, 2, 6, 7], 7))

"""
        def dfs(start, target, path):
            if target == 0:
                res.append(path.copy())
                return
            if target < 0:
                return

            for i in range(start, len(candidates)):
                path.append(candidates[i])
                dfs(i, target - candidates[i], path)
                path.pop()  # 回溯
                
                dfs(0, target, [])
        return res
"""
